//节点类

class Node{
    constructor(element){
        this.element = element;
        this.prev = null;
        this.next = null;
    }
}

//双向链表

class DoubleList{
    constructor(){
        this.head = null;  //记录首节点
        this.tail = null;  //记录尾节点
        this.count = 0;    //链表的节点数量
    }

    //从末尾添加
    push(element){
        //1.创建节点
        let node = new Node(element);
        //2.判断链表是否为空
        if(this.head === null){
            this.head = node;
            this.tail = node;
        }else{
            let last = this.tail;  //最后一个节点
            last.next = node;
            node.prev = last;
            this.tail = node;
        }
        this.count++;
    }

    //找到指定节点
    getNode(index){   //0
        let current = this.head;
        for(let i = 0; i < index;i++){
            current = current.next;
        }
        return current
    }

    //插入
    insert(element,index){
        //边界值的判断
        if(index >= 0 && index <= this.count){ //index = this.count  在末尾插入
            //创建新节点
            let node = new Node(element);
            if(index === 0){
                //1.在开头插入
                if(this.head === null){
                    //1.1  链表为空
                    this.head = node;
                    this.tail = node;
                }else{
                    //1.2  链表不为空
                    let current = this.head;
                    this.head = node;
                    current.prev = node;
                    node.next = current;
                }
            }else if(index === this.count){
                //2.在末尾插入
                let last = this.tail;
                last.next = node;
                node.prev = last;
                this.tail = node;
            }else{
                //3.在中间插入

                let current = this.getNode(index);  //当前的节点

                let prev = current.prev;

                prev.next = node;
                node.prev = prev;

                node.next = current;
                current.prev = node;

            }
            this.count++;
        }else{
            return false
        }
    }

    //删除
    removeAt(index){
        //1.边界值的判断
        if(index >= 0 && index < this.count){
            if(index === 0){
                //1.在开头删除
                if(this.count === 1){
                    //只有一个节点
                    this.head = null;
                    this.tail = null;
                }else{
                    //1.2不止有一个节点
                    let current = this.head;
                    current.next.prev = null;
                    this.head = current.next;
                }
            }else if(index === (this.count-1)){
                //2.在末尾删除

            }else{
                //3.在中间删除

            }
        }else{
            return undefined
        }
    }
}

let d = new DoubleList();

d.push('a');

d.push('b');

// d.insert('p',0)

// d.insert('x',0)

// d.insert('z',2) 

// d.insert('y',1)//x y p z

d.removeAt(0);

console.log(d);
// 1.单向链表  2，双向链表